package com.leetcode.LC;

public class LC35 {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        if (target < nums[0]) {
            return 0;
        } else if (target > nums[nums.length - 1]) {
            return nums.length;
        }
        int a = 0, b = nums.length - 1, mid = 0;
        while (a <= b) {
            mid = a + (b - a) / 2 ;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                a = mid + 1;
            } else if (nums[mid] > target) {
                b = mid - 1;
            }
        }

        if (nums[mid] < target)
            return mid + 1;
        else
            return mid;
    }

    public static void main(String[] args) {
        System.out.println(new LC35().searchInsert(new int[]{1, 3, 5, 6}, 2));

    }
}
